Leetcode 152.乘积最大子数组

题目描述：

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

1
2
3

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

1
2
3

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

链接：

https://leetcode-cn.com/problems/maximum-product-subarray

题目分析

  这道题跟 Leetcode 53.最大子序和 有点相似，我们当时采用的是动态规划的方法，对于每个数字都选择是否要将其加入前面的子数组中或者单独作为一个新子数组的开始，这道题能不能用同样的方法呢？答案是不能的。因为乘积并不符合“最优子结构”的定义。比如前面子数组的乘积是一个负数，现在乘上一个正数只会“负的更多”，但是如果后面出现了一个负数，乘上之后可以变得更大。因此当前位置的最优解并不一定是前一个位置的最优解转移得到的。
  通过上面的分析我们可以知道其实原因出在负数上面，那我们先分开讨论试试。如果当前位置是一个负数，则我们希望前面子数组的乘积也是负数，并尽可能“负的更多”，这样得到的结果是最大的。如果当前位置是一个正数，则我们希望前面子数组的乘积也是正数，并且尽可能“正的更多”。而其实“负的更多”也是由两个绝对值更大的正负数相乘得到的，那么实际上我们只需要维护两个动态转移的数，一个是最大数 Max，一个是最小数 Min，分别用于存放“正的更多”和“负的更多”两个数。对于每一个状态，将 nums[i]、Max*nums[i]、Min*nums[i] 三个数的最大值更新为 Max，最小值更新为 Min。并且记录遍历过程中出现过最大的 Max 即可。
  这里需要注意一个细节：不能直接将最大值赋给 Max，因为参与下面获取最小值的运算所需要的 Max 是上一个状态的。为了代码美观我们使用了两个变量 newMax 和 newMin 用于临时存放运算结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int Min = 1, Max = 1, newMax, newMin, result = INT_MIN;
        for(int i = 0; i < nums.size(); i++){
            newMax = max(nums[i], max(Max*nums[i], Min*nums[i]));
            newMin = min(nums[i], min(Max*nums[i], Min*nums[i]));
            Max = newMax;
            Min = newMin;
            result = max(result, Max);
        }
        return result;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是数组的长度。我们只对数组进行了一次遍历。
  空间复杂度：$O(1)$。我们只需要常数个变量的空间。